
#include <cstring>
#include <cstddef>
#include <iostream>


namespace rais {
namespace study {

using std::size_t;
using std::strlen;

//return -1 if does not find
size_t kmp_find(const char* s, const char* p, size_t slen = -1, size_t plen = -1) noexcept{
	//s:  target string
	//p: pattern string
	if(s == nullptr || p == nullptr) return -1;
	//assume s and p both are zero-ending string 
	if(*p == '\0') return 0; // p == ""

	if(slen == size_t(-1)) slen = strlen(s);
	if(plen == size_t(-1)) plen = strlen(p);
	if(slen < plen) return -1;

	size_t next[plen] = {0};
	//generate next[] array
	for(size_t i = 1, j = 0; i < plen - 1; ++i) {
		while(p[i] != p[j] && j != 0) j = next[j];
		if(p[i] == p[j]) ++j;
		next[i + 1] = j;
	}

	//find
	for(size_t i = 0, j = 0; i < slen; ++i) {
		while(s[i] != p[j] && j != 0) j = next[j];
		if(s[i] == p[j]) ++j;
		if(j >= plen) return i + 1 - plen;
	}
	return -1;
}

const char* kmp_find_ptr(const char* s, const char* p, size_t plen = -1) noexcept{
	if(s == nullptr || p == nullptr) return nullptr;
	if(*p == '\0') return s; // p == ""
	if(plen == size_t(-1)) plen = strlen(p);

	const char* next[plen]; // next[0] is a dummy

	//generate next[]
	for(const char* i = p, * j = p; i != p + plen - 1; ++i) {
		while(j != p && *i != *j) j = next[j - p];
		next[i - p + 1] = j == p ? j++ /* p */ : ++j /* j + 1 */;
	}

	//find
	for(const char* i = s, * j = p; *i != '\0'; ++i) {
		while(j != p && *i != *j) j = next[j - p];
		if(*i == *j) ++j;
		if(*j == '\0') return i + 1 - plen;
	}
	return nullptr;

}

} //namespace study
} //namespace rais

int main() {
	using std::cout;
	cout << rais::study::kmp_find("abaabababababbbababbabbbbabacbabababbb", "aabab") << std::endl;
	const char* str = "abaabababababbbababbabbbbabacbabababbb";
	const char* pos = rais::study::kmp_find_ptr(str, "aabab");
	if(pos == nullptr) cout << "not found";
	else               cout << size_t(pos - str);
	return 0;
}


